package DataStructure.linkList;

import java.util.HashSet;

/**
 * 142. 环形链表 II https://leetcode.cn/problems/linked-list-cycle-ii/
 * 题目简述：给定一个链表的头节点head，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 */
public class DetectCycle {

    /**
     * 思路一：快慢指针
     * slow一次走一步，fast一次走两步，如果链表不存在环则fast最终会指向null，如果存在环则这两个指针一定会在环中相遇
     * 设链表的总节点数为a+b，a为从链头到入环前一个节点的长度，b为环的长度。设相遇时slow走了s步，fast走了f步，则f=s+nb，即相遇时fast比slow多走了n圈环
     * 又f是s的两倍，f=2s。故有f=2nb，s=nb。那么slow再走a步必定走到入环节点，因此此时再定义一个指针p指向head，与slow同时走，当相遇时即为入环节点
     */
    public ListNode detectCycle(ListNode head) {
        //养成良好习惯
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
                if (slow == fast) {
                    ListNode p = head;
                    while(p != slow) {
                        p = p.next;
                        slow = slow.next;
                    }
                    return p;
                }
            }
        }
        return null;
    }

    /**
     * 思路二：哈希表
     */
    public ListNode detectCycle2(ListNode head) {
        ListNode p = head;
        HashSet<ListNode> hSet = new HashSet<>();
        while(p != null) {
            if(!hSet.add(p)) return p;
            p = p.next;
        }
        return null;
    }
}
